package com.itheima.algorithm.datastructure;

/**
 * 判断链表是否有环
 * @Author: zhangshao
 * @Since: 2024/5/7 17:19
 */
public class Leetcode141 {
	public static boolean hasCycle(ListNode head){
		// 兔
		ListNode h = head;
		// 龟
		ListNode t = head;

		while(h!=null && h.next!=null){
			// 还没走到终点

			t = t.next;
			h = h.next.next;
			if(h == t){
				//有环
				return true;
			}
		}
		return false;
	}

	public static void main(String[] args) {

		ListNode n10 = new ListNode(2,null);
		ListNode n9 = new ListNode(2,n10);
		ListNode n8 = new ListNode(2,n9);
		ListNode n7 = new ListNode(2,n8);
		ListNode n6 = new ListNode(1,n7);
		ListNode n5 = new ListNode(2,n6);
		ListNode n4 = new ListNode(2,n5);
		ListNode n3 = new ListNode(2,n4);
		ListNode n2 = new ListNode(2,n3);
		ListNode n1 = new ListNode(1,n2);


		System.out.println(hasCycle(n1));

	}
}
